package medium;

import java.util.ArrayList;
import java.util.List;

public class Lc2397 {
    class Solution {
        private int colCnt;

        private List<Integer> colSelectList = new ArrayList<>();

        public int maximumRows(int[][] matrix, int numSelect) {
            this.colCnt = matrix[0].length;

            List<Integer> lineBits = new ArrayList<>(matrix.length);
            for (int[] ints : matrix) {
                StringBuilder line = new StringBuilder();
                for (int j = 0; j < matrix[0].length; j++) {
                    line.append(ints[j]);
                }
                lineBits.add(Integer.parseInt(line.toString(), 2));
            }
            dfs("", 0, numSelect);
            // System.out.println(colSelectList.toString());

            int ret = 0;
            for (Integer colSelect : colSelectList) {
                int coverRow = 0;
                for (Integer lineBit : lineBits) {
                    if ((colSelect | lineBit) == colSelect) {
                        coverRow += 1;
                    }
                }
                ret = Math.max(coverRow, ret);
            }
            return ret;
        }

        private void dfs(String s, int index, int remainOneCnt) {
            if (index > colCnt) {
                colSelectList.add(Integer.parseInt(s, 2));
                return;
            }
            if (remainOneCnt == colCnt - index) {
                s += "1".repeat(colCnt - index);
                dfs(s, colCnt + 1, 0);
                return;
            }
            if (remainOneCnt == 0) {
                s += "0".repeat(colCnt - index);
                dfs(s, colCnt + 1, 0);
                return;
            }
            dfs(s + "0", index + 1, remainOneCnt);
            dfs(s + "1", index + 1, remainOneCnt - 1);
        }
    }
}
